package 力扣.动态规划.区间DP;

import java.util.ArrayList;
import java.util.List;

public class 分割等和子集416 {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0){
            return false;
        }
        int sum =  0;
        for (int t:nums) {
            sum += t;
        }
        if ((sum & 0x01) == 1){//为奇数，无法切分
            return false;
        }
        final int V = sum >> 1;
/*        List<Integer> list = new ArrayList<>();//使用集合超出内存空间
        list.add(0);*/
        boolean[] dp = new boolean[V + 1];//使用数组
        dp[0] = true;
        int p = 0;
        for (int x:nums) {
            for (int i = p; i >= 0 ; i--) {//因为都是正整数，所以可以从后往前更新点集
                if (dp[i]){
                    int newNum = i + x;
                    if (newNum <= V){//新的点集必须小于等于V
                        if (newNum == V){
                            return true;//找到
                        }else {
                            dp[newNum] = true;
                        }
                        p = Math.max(p, newNum);//更新可到达的区间范围
                    }
                }
            }
        }
        return false;
    }
    public boolean canPartition2(int[] nums) {
          if (nums == null || nums.length == 0){
              return false;
          }
          final  int N = nums.length;
          int sum = 0;
        for (int t:nums) {
            sum += t;
        }
        if ((sum & 0x01) == 1){
            return false;
        }
        final int V = (sum >> 1);
        boolean[] dp = new boolean[V + 1];
        dp[0] = true;
        for (int t:nums) {
            for (int i = V; i >= t ; i--) {//从大到小，可以保证只用一次t
                int prenums = i - t;
                int thisnums =  i;
                if (dp[prenums]){//存在
                    dp[thisnums] = true;//更新现在的
                }
            }
        }
        return dp[V];
    }


    public boolean canPartition3(int[] nums) {
         if (nums == null || nums.length == 0){
             return false;
         }
         int sum = 0;
        for (int t:nums) {
            sum += t;
        }
        if ((sum & 0x01) == 1){
            return false;
        }
        final int V = sum >> 1;//背包容量
        boolean[] dp = new boolean[V + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = V; j >= num; j--) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }
        return dp[V];
    }
}
